#include "StdAfx.h"
#include "binary_tree.h"


binary_tree::binary_tree()
	:root_(NULL)
{
}


binary_tree::~binary_tree()
{
	destroy(root_);
}
void binary_tree::destroy(node* nd)
{
	if (NULL == nd)
	{
		return;
	}
	destroy(nd->left);
	destroy(nd->right);
	delete nd;
	--size_;
}
void binary_tree::insert(const D& d)
{
	node* new_node = new node();
	new_node->data = d;
	if (!insert(root_, new_node))
	{
		delete new_node;
		new_node = NULL;
	}
}
void binary_tree::remove(const D& d)
{
	remove(root_, d);
}
bool binary_tree::insert(node* &nd, node* &new_node)
{
	if (NULL == nd)
	{
		++size_;
		nd = new_node;
		return true;
	}

	if (new_node->data < nd->data)
	{
		return insert(nd->left, new_node);
	}
	if (new_node->data > nd->data)
	{
		return insert(nd->right, new_node);
	}
	return false;
	
}

void binary_tree::remove(node* &nd, const D& d)
{
	if (NULL == nd)
	{
		return;
	}
	if (d < nd->data)
	{
		remove(nd->left, d);
		return;
	}
	if (d > nd->data)
	{
		remove(nd->right, d);
		return;
	}

	node* tmp = nd;

	if (NULL == nd->left)
	{
		nd = nd->right;
	} else if (NULL == nd->right)
	{
		nd = nd->left;
	} else
	{
		insert(nd->left, nd->right);
	}
	delete tmp;
	tmp = NULL;
}
void binary_tree::print(node* nd)
{
	if (NULL == nd)
	{
		return;
	}
	cout<<nd->data<<endl;
	print(nd->left);
	print(nd->right);
}
void binary_tree::print()
{
	print(root_);
}

const size_t binary_tree::size()
{
	return size_;
}

size_t binary_tree::deep()
{
	size_t dp = -1;
	deep(root_, dp);
	return dp;
}

void binary_tree::deep(node* &nd, size_t& dp)
{
	if (NULL == nd)
	{
		return;
	}
	size_t tmp = ++dp;
	deep(nd->left, tmp);
	deep(nd->right, dp);

	if (tmp > dp)
	{
		dp = tmp;
	}
}